package algebra.cost;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import utils.exception.CostEstimateException;

import kb.DescriptionLogicsKB;

import algebra.op.AlgebraicOP;
import algebra.op.JoinOP;

public class IntersectionGrouping {

	private final DescriptionLogicsKB kb;
	private AlgebraicOP result;
	private double mincost;
	private final JoinOP ip;

	public IntersectionGrouping(JoinOP ip, DescriptionLogicsKB kb) {
		this.kb = kb;
		this.ip = ip;
		result = null;
		mincost = 0.0;
	}

	public AlgebraicOP getBestOrderPlan() {
		return this.result;
	}

	public double getBestPlanCost() {
		return this.mincost;
	}

	/*
	 * Only left-deep trees are considered
	 */
	public void selectIntersectionOrder() {
		Set<AlgebraicOP> ops = new HashSet<AlgebraicOP>(ip.flattenedView());
		Map<Set<AlgebraicOP>, AlgebraicOP> plans = new HashMap<Set<AlgebraicOP>, AlgebraicOP>();
		Map<Set<AlgebraicOP>, Double> costs = new HashMap<Set<AlgebraicOP>, Double>();
//		computeIntersectionCost(ops, plans, costs);
		try {
			result = joinOrderOpt(ops, plans, costs);
		} catch (CostEstimateException e) {
			e.printStackTrace();
		}
//		result = plans.get(ops);
		mincost = costs.get(ops);
		// System.out.println("\nFor intersection opeartion: "+ops);
		// System.out.println("Plan: "+plans.get(ops));
		// System.out.println("Cost: "+costs.get(ops));
	}
	
	private double getPlanCostForJoins(Map<Set<AlgebraicOP>, AlgebraicOP> plans,
			Map<Set<AlgebraicOP>, Double> costs, Set<AlgebraicOP> join){
		if(plans.containsKey(join)){
			return costs.get(join);
		}else{
			try {
				PlanEstimation pe = new PlanEstimation(kb);
				AlgebraicOP joinplan = joinOrderOpt(join, plans, costs);
				double cost = pe.getPlanCost(joinplan);
				plans.put(join, joinplan);
				costs.put(join, cost);
				return cost;
			} catch (CostEstimateException e) {
				e.printStackTrace();
			}
		}
		return Double.MAX_VALUE;
	}
	//Selinger algorithm for join orders: only left-deep tree
	private AlgebraicOP joinOrderOpt(Set<AlgebraicOP> ops,
			Map<Set<AlgebraicOP>, AlgebraicOP> plans,
			Map<Set<AlgebraicOP>, Double> costs) throws CostEstimateException {
		PlanEstimation pe = new PlanEstimation(kb);
		if (ops.size() < 1 || plans.containsKey(ops)) {
			return null;
		}
		if (ops.size() == 1) {
			AlgebraicOP op = ops.iterator().next();
			plans.put(ops, op);
			costs.put(ops, pe.getPlanCost(op));
			return op;
		}else{
			//opt.size >= 2
			double mincost = Double.MAX_VALUE;
			AlgebraicOP bestjoin = null;
			for(AlgebraicOP cop : ops){
				Set<AlgebraicOP> others = new HashSet<AlgebraicOP>(ops);
				others.remove(cop);
				Set<AlgebraicOP> cops = new HashSet<AlgebraicOP>();
				cops.add(cop);
				//consider others join cop, only left deep
				double cost = this.getPlanCostForJoins(plans, costs, others) + 
						this.getPlanCostForJoins(plans, costs, cops);
				AlgebraicOP bestsub = plans.get(others);
				AlgebraicOP thisjoin = new JoinOP(bestsub, cop);
				cost += pe.getPlanCost(thisjoin);
				if(mincost > cost){
					mincost =cost;
					bestjoin = thisjoin;
				}
				plans.put(ops, bestjoin);
				costs.put(ops, mincost);
			}
			return bestjoin;
		}
	}

	// the cost is the size of the intermediate intersection, excluding single Q
	// or full Q
	private void computeIntersectionCost(Set<AlgebraicOP> ops,
			Map<Set<AlgebraicOP>, AlgebraicOP> plans,
			Map<Set<AlgebraicOP>, Double> costs) {
		if (ops.size() < 1 || plans.containsKey(ops)) {
			return;
		}
		if (ops.size() == 1) {
			AlgebraicOP op = ops.iterator().next();
			plans.put(ops, op);
			// no cost
			costs.put(ops, 0.0);
		} else if (ops.size() == 2) {
			Iterator<AlgebraicOP> itr = ops.iterator();
			AlgebraicOP op1 = itr.next();
			AlgebraicOP op2 = itr.next();
			SizeEstimation se = new SizeEstimation(kb);
			AlgebraicOP plan = null;
			if (se.sizeofOP(op1) <= se.sizeofOP(op2)) {
				// left arg is smaller
				plan = new JoinOP(op1, op2);
			} else {
				plan = new JoinOP(op2, op1);
			}
			plans.put(ops, plan);
			// no cost
			costs.put(ops, 0.0);
		} else {
			// another loop for selecting a single OP at a time
			SizeEstimation se = new SizeEstimation(kb);
			Iterator<AlgebraicOP> itr = ops.iterator();
			double mincost = Double.MAX_VALUE;
			AlgebraicOP left = null, right = null;
			while (itr.hasNext()) {
				AlgebraicOP rop = itr.next();
				Set<AlgebraicOP> lps = new HashSet<AlgebraicOP>(ops);
				lps.remove(rop);
				computeIntersectionCost(lps, plans, costs);
				double curcost = se.sizeofOP(plans.get(lps)) + costs.get(lps);
				if (curcost < mincost) {
					mincost = curcost;
					left = plans.get(lps);
					right = rop;
				}
			}
			plans.put(ops, new JoinOP(left, right));
			costs.put(ops, mincost);
		}
	}

}
